{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Rotting Oranges"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #breadth-first-search #array #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #广度优先搜索 #数组 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: orangesRotting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #腐烂的橘子"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>在给定的&nbsp;<code>m x n</code>&nbsp;网格<meta charset=\"UTF-8\" />&nbsp;<code>grid</code>&nbsp;中，每个单元格可以有以下三个值之一：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>值&nbsp;<code>0</code>&nbsp;代表空单元格；</li>\n",
    "\t<li>值&nbsp;<code>1</code>&nbsp;代表新鲜橘子；</li>\n",
    "\t<li>值&nbsp;<code>2</code>&nbsp;代表腐烂的橘子。</li>\n",
    "</ul>\n",
    "\n",
    "<p>每分钟，腐烂的橘子&nbsp;<strong>周围&nbsp;4 个方向上相邻</strong> 的新鲜橘子都会腐烂。</p>\n",
    "\n",
    "<p>返回 <em>直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回&nbsp;<code>-1</code></em>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/02/16/oranges.png\" style=\"height: 137px; width: 650px;\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[2,1,1],[1,1,0],[0,1,1]]\n",
    "<strong>输出：</strong>4\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[2,1,1],[0,1,1],[1,0,1]]\n",
    "<strong>输出：</strong>-1\n",
    "<strong>解释：</strong>左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个正向上。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[0,2]]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == grid.length</code></li>\n",
    "\t<li><code>n == grid[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 10</code></li>\n",
    "\t<li><code>grid[i][j]</code> 仅为&nbsp;<code>0</code>、<code>1</code>&nbsp;或&nbsp;<code>2</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [rotting-oranges](https://leetcode.cn/problems/rotting-oranges/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [rotting-oranges](https://leetcode.cn/problems/rotting-oranges/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[2,1,1],[1,1,0],[0,1,1]]', '[[2,1,1],[0,1,1],[1,0,1]]', '[[0,2]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orangesRotting(self, grid: List[List[int]]) -> int:\n",
    "        row, col = len(grid), len(grid[0])\n",
    "        rotting = {(i, j) for i in range(row) for j in range(col) if grid[i][j] == 2}\n",
    "        fresh = {(i, j) for i in range(row) for j in range(col) if grid[i][j] == 1}\n",
    "        timer = 0\n",
    "        while fresh:\n",
    "            if not rotting: return -1\n",
    "            rotting = {(i+di, j+dj) for i, j in rotting for di, dj in [(0, 1), (1, 0), (0, -1), (-1, 0)] if (i+di, j+dj) in fresh}\n",
    "            fresh -= rotting\n",
    "            timer += 1\n",
    "        return timer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orangesRotting(self, grid: 'List[List[int]]') -> 'int':\n",
    "        step=0\n",
    "        s=0\n",
    "        pres=0\n",
    "        for a in grid:\n",
    "            for b in a:\n",
    "                if b==1:\n",
    "                    s+=1\n",
    "\n",
    "        while s>0 and pres!=s:\n",
    "            step+=1\n",
    "            ngrid=[]\n",
    "            pres=s\n",
    "            s=0\n",
    "            for k in range(0,len(grid)):\n",
    "                row=grid[k]\n",
    "                r=[0]*len(row)\n",
    "                for i in range(0,len(row)):\n",
    "                    if row[i]==2:\n",
    "                        r[i]=2\n",
    "                    elif row[i]==1:\n",
    "                        if i>0 and row[i-1]==2:\n",
    "                            r[i]=2\n",
    "                        elif i<(len(row)-1) and row[i+1]==2:\n",
    "                            r[i]=2\n",
    "                        elif k>0 and grid[k-1][i]==2:\n",
    "                            r[i]=2\n",
    "                        elif k<(len(grid)-1 ) and grid[k+1][i]==2:\n",
    "                            r[i]=2\n",
    "                        else:\n",
    "                            r[i]=1\n",
    "\n",
    "                    if r[i] ==1:\n",
    "                        s+=1\n",
    "                ngrid.append(r)\n",
    "\n",
    "            grid=ngrid\n",
    "        if s==0 and step==0:\n",
    "            return 0\n",
    "        if pres==s:\n",
    "            return -1\n",
    "        return step"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orangesRotting(self, grid: 'List[List[int]]') -> 'int':\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        \n",
    "        import collections\n",
    "        queue = collections.deque()\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 2:\n",
    "                    queue.append((i, j, 0))\n",
    "        \n",
    "        def f(i, j):\n",
    "            for x, y in ((i-1,j), (i,j-1), (i+1,j), (i,j+1)):\n",
    "                if 0 <= x < m and 0 <= y < n:\n",
    "                    yield x, y\n",
    "        \n",
    "        res = 0\n",
    "        while queue:\n",
    "            i, j, res = queue.popleft()\n",
    "            for x, y in f(i, j):\n",
    "                if grid[x][y] == 1:\n",
    "                    grid[x][y] = 2\n",
    "                    queue.append((x, y, res+1))\n",
    "        \n",
    "        if any(1 in x for x in grid):\n",
    "            return -1\n",
    "        return res\n",
    "#     nb"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#\n",
    "# @lc app=leetcode.cn id=994 lang=python3\n",
    "#\n",
    "# [994] N 天后的牢房\n",
    "#\n",
    "# https://leetcode-cn.com/problems/rotting-oranges/description/\n",
    "#\n",
    "# algorithms\n",
    "# Easy (48.61%)\n",
    "# Total Accepted:    332\n",
    "# Total Submissions: 715\n",
    "# Testcase Example:  '[[2,1,1],[1,1,0],[0,1,1]]'\n",
    "#\n",
    "# 在给定的网格中，每个单元格可以有以下三个值之一：\n",
    "# \n",
    "# \n",
    "# 值 0 代表空单元格；\n",
    "# 值 1 代表新鲜橘子；\n",
    "# 值 2 代表腐烂的橘子。\n",
    "# \n",
    "# \n",
    "# 每分钟，任何与腐烂的橘子（在 4 个正方向上）相邻的新鲜橘子都会腐烂。\n",
    "# \n",
    "# 返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1。\n",
    "# \n",
    "# \n",
    "# \n",
    "# 示例 1：\n",
    "# \n",
    "# \n",
    "# \n",
    "# 输入：[[2,1,1],[1,1,0],[0,1,1]]\n",
    "# 输出：4\n",
    "# \n",
    "# \n",
    "# 示例 2：\n",
    "# \n",
    "# 输入：[[2,1,1],[0,1,1],[1,0,1]]\n",
    "# 输出：-1\n",
    "# 解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个正向上。\n",
    "# \n",
    "# \n",
    "# 示例 3：\n",
    "# \n",
    "# 输入：[[0,2]]\n",
    "# 输出：0\n",
    "# 解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。\n",
    "# \n",
    "# \n",
    "# \n",
    "# \n",
    "# 提示：\n",
    "# \n",
    "# \n",
    "# 1 <= grid.length <= 10\n",
    "# 1 <= grid[0].length <= 10\n",
    "# grid[i][j] 仅为 0、1 或 2\n",
    "# \n",
    "# \n",
    "#\n",
    "from queue import Queue\n",
    "dx = [0,0,-1,1]\n",
    "dy = [1,-1,0,0]\n",
    "class Solution:\n",
    "    def orangesRotting(self, grid: 'List[List[int]]') -> 'int':\n",
    "        n = len(grid)\n",
    "        if not n: return 0\n",
    "        m = len(grid[0])\n",
    "        q = Queue()\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j] == 2:\n",
    "                    q.put((i, j, 0))\n",
    "        ans = 0\n",
    "        while not q.empty():\n",
    "            a, b, c = q.get()\n",
    "            ans = max(ans, c)\n",
    "            for i in range(4):\n",
    "                xx = a + dx[i]\n",
    "                yy = b + dy[i]\n",
    "                if xx < 0 or xx >=n or yy < 0 or yy >=m or grid[xx][yy] != 1:\n",
    "                    continue\n",
    "                grid[xx][yy] = 2\n",
    "                q.put((xx, yy, c + 1))\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j] == 1:\n",
    "                    return -1\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import queue\n",
    "class Solution:\n",
    "    def orangesRotting(self, grid: 'List[List[int]]') -> 'int':\n",
    "        bad = set()\n",
    "        good = False\n",
    "        q = queue.Queue()\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] == 2:\n",
    "                    bad.add((i,j))\n",
    "                    q.put((i,j))\n",
    "                elif grid[i][j] == 1:\n",
    "                    good = True\n",
    "        if not good:\n",
    "            return 0\n",
    "        nrows = len(grid)\n",
    "        ncols = len(grid[0])\n",
    "        minte = -1\n",
    "        while not q.empty():\n",
    "            minte += 1\n",
    "            l = q.qsize()\n",
    "            for i in range(l):\n",
    "                p = q.get()\n",
    "                a, b = p[0] , p[1] -1\n",
    "                if 0<= a <nrows and 0<= b < ncols and (a,b) not in bad:\n",
    "                    if grid[a][b] == 1:\n",
    "                        grid[a][b] = 2\n",
    "                        bad.add((a,b))\n",
    "                        q.put((a,b))\n",
    "                a, b = p[0] , p[1] +1\n",
    "                if 0<= a <nrows and 0<= b < ncols and (a,b) not in bad:\n",
    "                    if grid[a][b] == 1:\n",
    "                        grid[a][b] = 2\n",
    "                        bad.add((a,b))\n",
    "                        q.put((a,b))\n",
    "                a, b = p[0] - 1, p[1]\n",
    "                if 0<= a <nrows and 0<= b < ncols and (a,b) not in bad:\n",
    "                    if grid[a][b] == 1:\n",
    "                        grid[a][b] = 2\n",
    "                        bad.add((a,b))\n",
    "                        q.put((a,b))\n",
    "                a, b = p[0] + 1, p[1]\n",
    "                if 0<= a <nrows and 0<= b < ncols and (a,b) not in bad:\n",
    "                    if grid[a][b] == 1:\n",
    "                        grid[a][b] = 2\n",
    "                        bad.add((a,b))\n",
    "                        q.put((a,b))\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] == 1:\n",
    "                    return -1\n",
    "        return minte\n",
    "                \n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orangesRotting(self, grid: 'List[List[int]]') -> 'int':\n",
    "        row, col = len(grid), len(grid[0])\n",
    "        stack, fresh = [], []\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if grid[i][j] == 2:\n",
    "                    stack.append((i, j))\n",
    "                elif grid[i][j] == 1:\n",
    "                    fresh.append((i, j))\n",
    "            \n",
    "        if not fresh: return 0\n",
    "        c = 0\n",
    "        while stack:\n",
    "            c += 1\n",
    "            length = len(stack)\n",
    "            for index in range(length):\n",
    "                i, j = stack.pop(0)\n",
    "                for pos in (i, j + 1), (i, j - 1), (i + 1, j), (i - 1, j):\n",
    "                    if pos in fresh:\n",
    "                        fresh.remove(pos)\n",
    "                        stack.append(pos)\n",
    "                        \n",
    "        if fresh: return -1\n",
    "                \n",
    "        return c - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import queue\n",
    "class Solution:\n",
    "    def bfs(self, grid, x, y):\n",
    "        visit = [[0 for i in range(len(grid[0]))]for j in range(len(grid))]\n",
    "        q = queue.Queue(100)\n",
    "        q.put([x,y,0])\n",
    "        direct = [[-1,0],[1,0],[0,-1],[0,1]]\n",
    "        while not q.empty():\n",
    "            now = q.get()\n",
    "            now_x = now[0]\n",
    "            now_y = now[1]\n",
    "            now_step = now[2]\n",
    "            visit[now_x][now_y] = 1\n",
    "            for item in direct:\n",
    "                next_x = now_x + item[0]\n",
    "                next_y = now_y + item[1]\n",
    "                if 0 <= next_x < len(grid) and 0 <= next_y < len(grid[0]):\n",
    "                    print(next_x,next_y)\n",
    "                    if visit[next_x][next_y]:\n",
    "                        continue\n",
    "                    if grid[next_x][next_y] == 2:\n",
    "                        return now_step+1\n",
    "                    if grid[next_x][next_y] == 1:\n",
    "                        q.put([next_x, next_y, now_step+1])\n",
    "        return -1\n",
    "        \n",
    "    def orangesRotting(self, grid):\n",
    "        res_max = -1\n",
    "        flag = False\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] == 1:\n",
    "                    flag = True\n",
    "        if flag == False:\n",
    "            return 0\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] == 1:\n",
    "                    res = self.bfs(grid, i, j)\n",
    "                    if res == -1:\n",
    "                        return -1\n",
    "                    res_max = max(res_max, res)\n",
    "        return res_max\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orangesRotting(self, grid: List[List[int]]) -> int:\n",
    "        queue = []\n",
    "        time = 0\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] == 2: queue.append((i, j, time))\n",
    "        \n",
    "        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]\n",
    "        while queue:\n",
    "            i, j, time = queue.pop(0)\n",
    "            for direction in directions:\n",
    "                new_i = i + direction[0]\n",
    "                new_j = j + direction[1]\n",
    "                if 0 <= new_i < len(grid) and 0 <= new_j < len(grid[0]) and grid[new_i][new_j] == 1:\n",
    "                    grid[new_i][new_j] = 2\n",
    "                    queue.append((new_i, new_j, time + 1))\n",
    "        \n",
    "        for i in range(len(grid)):\n",
    "            if 1 in grid[i]: return -1\n",
    "        return time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orangesRotting(self, grid: List[List[int]]) -> int:\n",
    "        if not grid: return 0\n",
    "        row = len(grid)\n",
    "        col = len(grid[0])\n",
    "        seen = set()\n",
    "        stack = []\n",
    "        count = 0\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if grid[i][j] == 2:\n",
    "                    stack.append((i,j))\n",
    "                    seen.add((i,j))\n",
    "                if grid[i][j] == 1:\n",
    "                    count += 1\n",
    "        if not count: return 0\n",
    "        res = -1\n",
    "        k = 0\n",
    "        while stack:\n",
    "            tmp = stack\n",
    "            stack = []\n",
    "            res += 1\n",
    "            for i,j in tmp:\n",
    "                for x,y in ((0,1),(0,-1),(-1,0),(1,0)):\n",
    "                    ti = i+x\n",
    "                    tj = j+y\n",
    "                    if 0<=ti<row and 0<=tj<col and (ti,tj) not in seen and grid[ti][tj] == 1:\n",
    "                        stack.append((ti,tj))\n",
    "                        seen.add((ti,tj))\n",
    "                        k += 1\n",
    "        return res if k == count else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orangesRotting(self, grid: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        queue = []\n",
    "        vis = [[0]*n for i in range(m)]\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 2:\n",
    "                    queue.append((i,j))\n",
    "                    vis[i][j] = 1\n",
    "        if not queue: \n",
    "            if sum([sum(row) for row in grid]):\n",
    "                return -1\n",
    "            else:\n",
    "                return 0\n",
    "        last = new = queue[-1]\n",
    "        # print(last)\n",
    "        step = 0\n",
    "        while queue:\n",
    "            x, y = queue.pop(0)\n",
    "            for i, j in [[0,1],[0,-1],[1,0],[-1,0]]:\n",
    "                nx, ny = x +i , y+j\n",
    "                if 0<= nx < m and 0 <= ny < n and not vis[nx][ny] and grid[nx][ny] == 1:\n",
    "                    queue.append((nx, ny))\n",
    "                    vis[nx][ny] = 1\n",
    "                    new = (nx, ny)\n",
    "            if (x,y) == last:\n",
    "                step += 1\n",
    "                last = new\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if not vis[i][j] and grid[i][j] == 1:\n",
    "                    return -1\n",
    "        return step - 1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orangesRotting(self, grid: List[List[int]]) -> int:\n",
    "        M = len(grid)\n",
    "        N = len(grid[0])\n",
    "        queue = []\n",
    "\n",
    "        count = 0  # count 表示新鲜橘子的数量\n",
    "        for r in range(M):\n",
    "            for c in range(N):\n",
    "                if grid[r][c] == 1:\n",
    "                    count += 1\n",
    "                elif grid[r][c] == 2:\n",
    "                    queue.append((r, c))\n",
    "\n",
    "        round = 0  # round 表示腐烂的轮数，或者分钟数\n",
    "        while count > 0 and len(queue) > 0:  # 还有好橘子且队列还有坏橘子\n",
    "            round += 1  # 层数+1\n",
    "            n = len(queue)  # 记录这一层的坏橘子数\n",
    "            for i in range(n):  # 遍历完这一层的坏橘子\n",
    "                r, c = queue.pop(0)  # 取出队列开头的坏橘子坐标\n",
    "                if r-1 >= 0 and grid[r-1][c] == 1:  # 右邻有好橘子\n",
    "                    grid[r-1][c] = 2  # 好橘子变坏\n",
    "                    count -= 1  # 好橘子数-1\n",
    "                    queue.append((r-1, c))  # 新变坏的这只橘子进入坏橘子队列\n",
    "                if r+1 < M and grid[r+1][c] == 1:  # 左邻有好橘子\n",
    "                    grid[r+1][c] = 2\n",
    "                    count -= 1\n",
    "                    queue.append((r+1, c))\n",
    "                if c-1 >= 0 and grid[r][c-1] == 1:  # 下邻有好橘子\n",
    "                    grid[r][c-1] = 2\n",
    "                    count -= 1\n",
    "                    queue.append((r, c-1))\n",
    "                if c+1 < N and grid[r][c+1] == 1:  # 上邻有好橘子\n",
    "                    grid[r][c+1] = 2\n",
    "                    count -= 1\n",
    "                    queue.append((r, c+1))\n",
    "\n",
    "        if count > 0:  # 还有好橘子\n",
    "            return -1\n",
    "        else:  # 没有好橘子了\n",
    "            return round"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.Good = 1\n",
    "        self.Rot = 2\n",
    "        self.directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]\n",
    "\n",
    "    def orangesRotting(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        queue = deque()\n",
    "        # 先把腐烂的橘子都放进来，定义新鲜橘子的地方path距离是0\n",
    "        global d\n",
    "        for row in range(m):\n",
    "            for col in range(n):\n",
    "                if grid[row][col] == self.Rot:\n",
    "                    queue.append((row, col, 0))\n",
    "\n",
    "        # 多源同时进行BFS\n",
    "        while queue:\n",
    "            row, col, d = queue.popleft()\n",
    "            for direction in self.directions:\n",
    "                new_row = row + direction[0]\n",
    "                new_col = col + direction[1]\n",
    "                if  0 <= new_row <= m -1 and 0 <= new_col <= n -1 and grid[new_row][new_col] == self.Good:\n",
    "                    grid[new_row][new_col] = 2\n",
    "                    queue.append((new_row, new_col, d + 1))\n",
    "\n",
    "        if any(1 in row for row in grid):\n",
    "            return -1\n",
    "        return d\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orangesRotting(self, grid: List[List[int]]) -> int:\n",
    "        t = 0\n",
    "        good = set()\n",
    "        bad =set()\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] == 1:\n",
    "                    good.add((i, j))\n",
    "                elif grid[i][j] == 2:\n",
    "                    bad.add((i, j))\n",
    "        #print(good)\n",
    "        while good:\n",
    "            #print(bad)\n",
    "            new_bad = set()\n",
    "            for n in bad:\n",
    "                if (n[0]+1, n[1]) in good:\n",
    "                    good.remove((n[0]+1, n[1]))\n",
    "                    new_bad.add((n[0]+1, n[1]))\n",
    "                if (n[0]-1, n[1]) in good:\n",
    "                    good.remove((n[0]-1, n[1]))\n",
    "                    new_bad.add((n[0]-1, n[1]))\n",
    "                if (n[0], n[1]+1) in good:\n",
    "                    good.remove((n[0], n[1]+1))\n",
    "                    new_bad.add((n[0], n[1]+1))\n",
    "                if (n[0], n[1]-1) in good:\n",
    "                    good.remove((n[0], n[1]-1))\n",
    "                    new_bad.add((n[0], n[1]-1))\n",
    "            t += 1\n",
    "            if not new_bad:\n",
    "                break\n",
    "            bad = new_bad\n",
    "        if good:\n",
    "            return -1\n",
    "        return t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orangesRotting(self, grid: List[List[int]]) -> int:\n",
    "        if not grid or not grid[0]:\n",
    "            return 0\n",
    "        \n",
    "        row, col = len(grid), len(grid[0])\n",
    "        rotten = collections.deque()\n",
    "        fresh_num = 0\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if grid[i][j] == 1:\n",
    "                    fresh_num += 1\n",
    "                elif grid[i][j] == 2:\n",
    "                    rotten.append((i, j))\n",
    "        \n",
    "        minutes = 0\n",
    "        while rotten and fresh_num > 0:\n",
    "            minutes += 1\n",
    "            for _ in range(len(rotten)):\n",
    "                x, y = rotten.popleft()\n",
    "                for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):\n",
    "                    xx, yy = x + i, y + j\n",
    "                    if xx < 0 or xx >= row or yy < 0 or yy >= col or grid[xx][yy] != 1:\n",
    "                        continue\n",
    "                    grid[xx][yy] = 2\n",
    "                    fresh_num -= 1\n",
    "                    rotten.append((xx, yy))\n",
    "        return minutes if fresh_num == 0 else -1\n",
    "                            \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orangesRotting(self, grid: 'List[List[int]]') -> 'int':\n",
    "        # 将坏苹果的位置和次数记录下来\n",
    "        x, y, res = len(grid), len(grid[0]), 0\n",
    "        locs, stack = [[-1, 0], [0, -1], [0, 1], [1, 0]], []\n",
    "        for i in range(x):\n",
    "            for j in range(y):\n",
    "                if grid[i][j] == 2:\n",
    "                    stack.append((i, j, 0))\n",
    "        while stack:\n",
    "            i, j, res = stack.pop(0)\n",
    "            for loc in locs:\n",
    "                loc_i, loc_j = i+loc[0], j+loc[1]\n",
    "                if 0 <= loc_i < x and 0 <= loc_j < y and grid[loc_i][loc_j] == 1:\n",
    "                    grid[loc_i][loc_j] = 2\n",
    "                    stack.append((loc_i, loc_j, res+1))\n",
    "        for i in range(x):\n",
    "            for j in range(y):\n",
    "                if grid[i][j] == 1:\n",
    "                    return -1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def orangesRotting(self, grid):\n",
    "        R, C = len(grid), len(grid[0])\n",
    "\n",
    "        # queue - all starting cells with rotting oranges\n",
    "        queue = collections.deque()\n",
    "        for r, row in enumerate(grid):\n",
    "            for c, val in enumerate(row):\n",
    "                if val == 2:\n",
    "                    queue.append((r, c, 0))\n",
    "\n",
    "        def neighbors(r, c):\n",
    "            for nr, nc in ((r-1,c),(r,c-1),(r+1,c),(r,c+1)):\n",
    "                if 0 <= nr < R and 0 <= nc < C:\n",
    "                    yield nr, nc\n",
    "\n",
    "        d = 0\n",
    "        while queue:\n",
    "            r, c, d = queue.popleft()\n",
    "            for nr, nc in neighbors(r, c):\n",
    "                if grid[nr][nc] == 1:\n",
    "                    grid[nr][nc] = 2\n",
    "                    queue.append((nr, nc, d+1))\n",
    "\n",
    "        if any(1 in row for row in grid):\n",
    "            return -1\n",
    "        return d\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def orangesRotting(self, grid: List[List[int]]) -> int:\n",
    "        from sys import maxsize\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        cost = [[maxsize for _ in range(m)] for _ in range(n)]\n",
    "        ans = 0\n",
    "\n",
    "        def dfs(i, j, ts):\n",
    "            if i < 0 or i == n or j < 0 or j == m:\n",
    "                return\n",
    "            if ts > 0 and grid[i][j] != 1:\n",
    "                return\n",
    "            if ts > 0 and cost[i][j] <= ts:\n",
    "                return\n",
    "            cost[i][j] = ts\n",
    "            dfs(i - 1, j, ts + 1)\n",
    "            dfs(i, j - 1, ts + 1)\n",
    "            dfs(i + 1, j, ts + 1)\n",
    "            dfs(i, j + 1, ts + 1)\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j] == 2:\n",
    "                    dfs(i, j, 0)\n",
    "                    \n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j] == 1 and cost[i][j] == maxsize:\n",
    "                    #print(i,j,cost[i][j])\n",
    "                    return -1\n",
    "                if cost[i][j] != maxsize:\n",
    "                    ans = max(ans, cost[i][j])\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orangesRotting(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        count = 0\n",
    "        queue = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    count += 1\n",
    "                elif grid[i][j] == 2:\n",
    "                    queue.append((i, j))\n",
    "        \n",
    "        round = 0\n",
    "        while count and queue:\n",
    "            round += 1\n",
    "            length = len(queue)\n",
    "            for _ in range(length):\n",
    "                r, c = queue.pop(0)\n",
    "                for ni, nj in [(r-1, c), (r+1, c), (r, c-1), (r, c+1)]:\n",
    "                    if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == 1:\n",
    "                        count -= 1\n",
    "                        grid[ni][nj] = 2\n",
    "                        queue.append((ni, nj))\n",
    "        \n",
    "        if count:\n",
    "            return -1\n",
    "        else:\n",
    "            return round "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]\n",
    "    def orangesRotting(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        fresh = set()\n",
    "        rotted = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    fresh.add((i,j))\n",
    "                if grid[i][j] == 2:\n",
    "                    rotted.append((i,j))\n",
    "        if len(fresh) == 0:\n",
    "            return 0\n",
    "        minutes = 0\n",
    "        while rotted:\n",
    "            length = len(rotted)\n",
    "            for k in range(length):\n",
    "                top = rotted.pop(0)\n",
    "                for d in self.directions:\n",
    "                    new_i = top[0] + d[0]\n",
    "                    new_j = top[1] + d[1]\n",
    "                    if 0 <= new_i < m and 0 <= new_j < n and grid[new_i][new_j] == 1:\n",
    "                        rotted.append((new_i, new_j))\n",
    "                        fresh.remove((new_i, new_j))\n",
    "                        grid[new_i][new_j] = 2\n",
    "            minutes += 1\n",
    "        return -1 if fresh else minutes-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orangesRotting(self, grid: List[List[int]]) -> int:\n",
    "        direction = [(-1,0),(1,0),(0,-1),(0,1)]\n",
    "        count =0\n",
    "        stack =[]\n",
    "        m= len(grid)\n",
    "        n =len(grid[0])\n",
    "        for r in range(m):\n",
    "            for c in range(n):\n",
    "                if grid[r][c] ==1:\n",
    "                    count +=1\n",
    "                if grid[r][c] == 2:\n",
    "                    stack.append([r,c])\n",
    "        if not count and not stack:\n",
    "            return 0\n",
    "\n",
    "        time = -1\n",
    "        while stack:\n",
    "            next =[]\n",
    "            for r, c in stack:\n",
    "                for dx,dy in direction:\n",
    "                    if 0<=r+dx<m and 0<=c+dy<n and grid[r+dx][c+dy] ==1:\n",
    "                        count -=1\n",
    "                        grid[r+dx][c+dy]=2\n",
    "                        next.append([r+dx,c+dy])\n",
    "            stack =next\n",
    "            time +=1\n",
    "\n",
    "        return time if not count else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "        \n",
    "\n",
    "    def orangesRotting(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        row = len(grid)#行\n",
    "        col = len(grid[0])#列\n",
    "        direction = [(1, 0), (-1, 0), (0, 1), (0, -1)]\n",
    "        count = 0\n",
    "        queue = []\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if grid[i][j] == 2:\n",
    "                    queue.append((i,j,count))\n",
    "        \n",
    "        while queue:\n",
    "            x,y, count= queue.pop(0)\n",
    "            for dx,dy in direction:\n",
    "                nx = x+dx\n",
    "                ny = y+dy\n",
    "                if 0<=nx<len(grid) and 0<=ny<len(grid[0]):\n",
    "                    if grid[nx][ny] ==1:\n",
    "                        grid[nx][ny] = 2\n",
    "                        queue.append((nx,ny,count+1))\n",
    "            print(count,grid)\n",
    "        \n",
    "        for row in grid:\n",
    "            if 1 in row:\n",
    "                return -1\n",
    "            \n",
    "        return count\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orangesRotting(self, grid: List[List[int]]) -> int:\n",
    "        self.count = 0\n",
    "        queue = []\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:\n",
    "                    self.count += 1\n",
    "                if grid[i][j]==2:\n",
    "                    queue.append([i,j])\n",
    "        def isIn(i, j):\n",
    "            if 0<=i<m and 0<=j<n: return True\n",
    "            return False\n",
    "        def tmp(grid, x, y, queue):\n",
    "            kv = [[x-1,y], [x+1,y], [x,y-1], [x,y+1]]\n",
    "            for i, j in kv:\n",
    "                if isIn(i, j) and grid[i][j]==1:\n",
    "                    grid[i][j] = 2\n",
    "                    self.count -= 1\n",
    "                    queue.append([i,j])\n",
    "\n",
    "        res = 0\n",
    "        while self.count>0 and len(queue)>0:\n",
    "            print('begin', res, self.count, queue)\n",
    "            res += 1\n",
    "            badCnt = len(queue)\n",
    "            for i in range(len(queue)):\n",
    "                x, y = queue.pop(0)\n",
    "                tmp(grid, x, y, queue)\n",
    "            print('done', res, self.count, queue)\n",
    "        if self.count>0: return -1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orangesRotting(self, grid: List[List[int]]) -> int:\n",
    "        dirs = [[0,1],[0,-1],[1,0],[-1,0]]\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        queue = []\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==2:\n",
    "                    queue.append([i,j])\n",
    "        \n",
    "        cnt = 0\n",
    "        while queue:\n",
    "            t = queue\n",
    "            queue = []\n",
    "            for i,j in t:\n",
    "                for d in dirs:\n",
    "                    di,dj = i+d[0],j+d[1]\n",
    "                    if 0<=di<m and 0<=dj<n and grid[di][dj]==1:\n",
    "                        grid[di][dj]=2\n",
    "                        queue.append([di,dj])\n",
    "            cnt += 1\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:\n",
    "                    return -1\n",
    "        if cnt==0:\n",
    "            return 0\n",
    "        return cnt-1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orangesRotting(self, grid: List[List[int]]) -> int:\n",
    "        status = []\n",
    "        flag = [[-1 for i in range(len(grid[0]))] for j in range(len(grid))]\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] == 2:\n",
    "                    status.append((i,j,0))\n",
    "                    flag[i][j] = 0  \n",
    "        head = 0\n",
    "        directions = [[0,1], [0,-1], [-1,0], [1, 0]]\n",
    "        while head < len(status):\n",
    "            curr_i, curr_j, time = status[head]\n",
    "            for direct in directions:\n",
    "                tgt_i, tgt_j = curr_i + direct[0], curr_j + direct[1]\n",
    "                if tgt_i >= 0 and tgt_i < len(grid) and tgt_j >= 0 and tgt_j < len(grid[0]):\n",
    "                    if flag[tgt_i][tgt_j] == -1 and grid[tgt_i][tgt_j] == 1:\n",
    "                        flag[tgt_i][tgt_j] = time + 1\n",
    "                        status.append((tgt_i, tgt_j, time+1))\n",
    "            head += 1\n",
    "        ans = 0\n",
    "        for i in range(len(flag)):\n",
    "            for j in range(len(flag[0])):\n",
    "                ans = max(ans, flag[i][j])\n",
    "                if flag[i][j] == -1 and grid[i][j] == 1:\n",
    "                    return -1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orangesRotting(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        q = []\n",
    "        res = 0\n",
    "        # 找出所有腐烂橘子的位置\n",
    "        count = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 2:\n",
    "                    q.append([i,j,0])\n",
    "                elif grid[i][j] == 1:\n",
    "                    count += 1\n",
    "\n",
    "        while q:\n",
    "            sx, sy, t = q.pop(0)\n",
    "            res = max(res, t)\n",
    "            for dx, dy in [(-1,0), (1,0),(0,1),(0,-1)]:\n",
    "                x = sx + dx\n",
    "                y = sy + dy\n",
    "                \n",
    "                if 0<=x<m and 0<=y<n and grid[x][y] == 1:\n",
    "                    grid[x][y] = 2\n",
    "                    count -= 1\n",
    "                    q.append([x, y, t + 1])\n",
    "            \n",
    "        return res if count==0 else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orangesRotting(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        q = deque()\n",
    "        res = 0\n",
    "        # 找出所有腐烂橘子的位置\n",
    "        count = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 2:\n",
    "                    q.append([i,j,0])\n",
    "                elif grid[i][j] == 1:\n",
    "                    count += 1\n",
    "\n",
    "        while q:\n",
    "            sx, sy, t = q.popleft()\n",
    "            res = max(res, t)\n",
    "            for dx, dy in [(-1,0), (1,0),(0,1),(0,-1)]:\n",
    "                x = sx + dx\n",
    "                y = sy + dy      \n",
    "                if 0 <= x < m and 0 <= y < n and grid[x][y] == 1:\n",
    "                    grid[x][y] = 2\n",
    "                    count -= 1\n",
    "                    q.append([x, y, t + 1])   \n",
    "        return res if count == 0 else -1\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
